// 给定整数数组arr，再给定一个整数k，要求返回数组arr中最小的k个数

// 思路1，堆排序的解法，把数组的前k个元素构造为大顶堆，遍历剩余[k, size - 1]的元素和堆顶元素的大小
// 如果比堆顶元素小，交换，再将这个k个元素调整为大顶堆，最后输出大顶堆的k个元素

function getLeastNumbers(nums, k) {
    let size = nums.length
    if (k <= 0 || !nums) {
        return []
    }
    buildMaxHeap(nums, k)
    for (let i = k; i < size; i++) {
        if (nums[0] > nums[i]) {
            [nums[0], nums[i]] = [nums[i], nums[0]];
            heapify(nums, 0, k - 1)
        }
    }
    return nums.slice(0, k)
}

function buildMaxHeap(nums, k) {
    for (let i = Math.floor((k - 1) / 2); i >= 0; i--) {
        heapify(nums, i, k - 1)
    }
}

function heapify(nums, start, end) {
    let left = 2 * start + 1
    let right = left + 1
    while (left <= end) {
        let maxIndex = start
        if (nums[left] > nums[maxIndex]) {
            maxIndex = left
        }
        if (right <= end && nums[right] > nums[maxIndex]) {
            maxIndex = right
        }
        if (maxIndex === start) {
            break
        }
        [nums[start], nums[maxIndex]] = [nums[maxIndex], nums[start]];
        start = maxIndex
        left = 2 * start + 1
        right = left + 1
    }
}

let arr = [3, 8, 5, 4, 7, 9, 2, 1]
let k = 2
console.log(getLeastNumbers(arr, k))

// 思路2，通过快速排序，在每次调整完后，都会确定一个元素的最终位置，以该位置为界限，左边子数组
// 的元素都比该元素小，右边子数组的元素都比该元素大
// 当某次划分正好是第k个元素下标，就找到了数组中最小的k个数对应的区间

function getLeastNumbers2(nums, k) {
    let size = nums.length
    if (k >= size) {
        return nums
    }
    return quickSort(nums, 0, nums.length - 1, k)
}

function quickSort(nums, low, high, k) {
    if (low < high) {
        let index = partition(nums, low, high)
        if (index === k) {
            return nums.slice(0, k)
        } else if (index < k) {
            quickSort(nums, index + 1, high, k)
        } else {
            quickSort(nums, low, index - 1, k)
        }
    }
    return nums.slice(0, k)
}

function partition(nums, low, high) {
    let pivot = Math.floor(Math.random() * (high - low)) + low
    let pivotVal = nums[pivot];
    [nums[pivot], nums[low]] = [nums[low],nums[pivot]];
    let i = low + 1
    for (let j = i; j <= high; j++) {
        if (nums[j] < pivotVal) {
            [nums[j], nums[i]] = [nums[i], nums[j]];
            i++
        }        
    }
    [nums[low], nums[i - 1]] = [nums[i - 1], nums[low]];
    return i - 1
}

let arr1 =  [3, 8, 5, 4, 7, 9, 2, 1]
let k1 = 2
console.log(getLeastNumbers2(arr1, k1));